package 算法.动态规划;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-14
 */
public class JZ19正则表达式匹配 {
    //动态规划
    public boolean match (String str, String pattern) {
        // write code here
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];
        //遍历str每个长度
        for(int i = 0; i <= n1; i++){
            //遍历pattern每个长度
            for(int j = 0; j <= n2; j++){
                //空正则的情况
                if(j == 0){
                    dp[i][j] = (i == 0 ? true : false);
                }//非空的情况下 星号、点号、字符
                else{
                    if(pattern.charAt(j - 1) != '*'){
                        //当前字符不为*，用.去匹配或者字符直接相同
                        if(i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')){
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }else{
                        // *
                        if(j >= 2){ // |=:两个二进制对应位都为0时，结果等于0，否则结果等于1；
                            dp[i][j] |= dp[i][j - 2];
                        }
                        ////若是前一位为.或者前一位可以与这个数字匹配
                        if(i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')){
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
            }
        }

        return  dp[n1][n2];
    }

    public boolean match2 (String str, String pattern) {
        if(str==null||pattern==null) return false;
        if(!check(pattern)) return false;
        int rows = str.length();
        int cols = pattern.length();
        boolean[][] dp = new boolean[rows+1][cols+1];
        //str做行，pattern做列的行列对应模型
        dp[0][0] = true;
        for(int col = 1;col<=cols;col++){
            for(int row = 0;row<=rows;row++){
                //看结尾位置(注意是[row-1]和[col-1]字符)
                char pEnd = pattern.charAt(col-1);
                if(pEnd=='*'){
                    //1.*前的玩意一次都不出现
                    //2.*前的玩意p和sEnd匹配,如果p出现若干次能够使得dp[row-1][col]为true，那再多一次就好了
                    dp[row][col] = dp[row][col-2] || (row>0 && isMatch(str.charAt(row-1),pattern.charAt(col-2))&&dp[row-1][col]);
                }else{
                    //如果不是*，那么只和左上角有关
                    dp[row][col] = row > 0 && isMatch(str.charAt(row-1),pEnd) && dp[row-1][col-1];
                }
            }
        }
        return  dp[rows][cols];
    }

    public boolean isMatch(char s,char p){
        return s==p||p=='.';
    }

    boolean check(String str){
        if("".equals(str)) return true;
        if(str.charAt(0)=='*') return false;
        for(int i = 1;i<str.length();i++){
            //两个*不能连着
            if(str.charAt(i)=='*'&&str.charAt(i-1)=='*'){
                return false;
            }
        }
        return  true;
    }
}
